home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / src / plane / _voronoi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.2 KB  |  124 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _voronoi.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/plane.h>
  17. #include <LEDA/plane_alg.h>
  18. #include <LEDA/delaunay_tree.h>
  19. #include <LEDA/d_array.h>
  20.  
  21.  
  22. declare2(d_array,point,node)
  23.  
  24. static d_array(point,node) V(nil);
  25.  
  26. static GRAPH(point,point)* G;
  27.  
  28. static double infi_length;
  29.  
  30. static point X;
  31.  
  32.  
  33. static void trace_segment(double x1, double y1, double x2, double y2, 
  34.                    double sx0, double sy0)
  35. {
  36.   point p(x1,y1);
  37.   point q(x2,y2);
  38.   point s(sx0,sy0);
  39.  
  40.   node v,w;
  41.  
  42.   if ((v = V[p]) == nil) V[p] = v = G->new_node(p);
  43.     
  44.   if ((w = V[q]) == nil) V[q] = w = G->new_node(q);
  45.  
  46.   G->new_edge(v,w,s);
  47.  
  48.  
  49. }
  50.  
  51.  
  52. static void infi_point(double x1, double y1, double x2, double y2, double* x, double* y)
  53. {
  54.   vector v(x2,y2);
  55.  
  56.   v = v.norm();
  57.  
  58.   *x = x1 + infi_length * v[0];
  59.   *y = y1 + infi_length * v[1];
  60.  
  61. }
  62.  
  63.  
  64. static int cmp_infi_pts(point& p, point& q)
  65. { // used to sort infi points clockwise around X
  66.   segment  s1(X,p);
  67.   segment  s2(X,q);
  68.   real a1 = s1.angle();
  69.   real a2 = s2.angle();
  70.   return compare(a2,a1); 
  71. }
  72.  
  73.  
  74. void VORONOI(list(point)& site_list, double R, GRAPH(point,point)& VD)
  75. { 
  76.    if (site_list.empty()) return;
  77.  
  78.    X = site_list.head();
  79.  
  80.    delaunay_tree DT;
  81.  
  82.    point p,q;
  83.    node v;
  84.  
  85.    list(point) infi_list;
  86.  
  87.    forall(p,site_list) DT.insert(p,0);
  88.  
  89.    infi_length = R;
  90.  
  91.    G = &VD;
  92.  
  93.    DT.trace_voronoi_edges(trace_segment, infi_point, 1);
  94.  
  95.  
  96.    // sort & link infinite points
  97.  
  98.    forall_nodes(v,VD) 
  99.      if (VD.outdeg(v) == 1) infi_list.append(VD[v]);
  100.  
  101.    infi_list.sort(cmp_infi_pts);
  102.  
  103.    point INFI(MAXDOUBLE,MAXDOUBLE);  
  104.  
  105.    list_item it;
  106.  
  107.    forall_items(it,infi_list)
  108.    {  node p = V[infi_list[it]];
  109.       node q = V[infi_list[infi_list.cyclic_succ(it)]];
  110.       point s = VD[VD.first_adj_edge(q)];
  111.       VD.new_edge(p,q,s); 
  112.     }
  113.  
  114.    forall_items(it,infi_list)
  115.    {  node p = V[infi_list[it]];
  116.       node q = V[infi_list[infi_list.cyclic_pred(it)]];
  117.       VD.new_edge(p,q,INFI);  
  118.     }
  119.  
  120.    V.clear();
  121.  
  122. }
  123.  
  124.